#include "common.h"

string minWindow(string s, string t)
{
	string ans("");
	int len = INT_MAX;
	int arr[128] = { 0 };
	for (int i = 0; i < t.size(); i++)
	{
		arr[t[i]]++;
	}
	int m = t.size();
	int mm = 0;
	int flg[128] = { 0 };
	int n = s.size();
	int left = 0;
	int right = 0;
	while (right < n)
	{
		if (arr[s[right]] == 0) right++;
		else
		{
			flg[s[right]]++;
			if (flg[s[right]] <= arr[s[right]])
				mm++;
			right++;
			while (left < right && (flg[s[left]] > arr[s[left]] || arr[s[left]] == 0))
			{
				if (arr[s[left]] != 0)
				{
					flg[s[left]]--;
				}
				left++;
			}
			if (mm == m)
			{
				if (right - left < len)
				{
					len = right - left;
					ans = s.substr(left, len);
				}
			}
		}
	}
	return ans;
}